package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;
import org.junit.Test;

/**
 * 【翻转链表】
 * 第一种递归方法，要想翻转head，只需要翻转head.next。比如原来顺序a->b->c->null
 * 翻转a.next后：a->b<-c null。此时实际上b.next指向null，c之前的null变成游离态
 *                 |->null
 * 这时把b.next指向a,a的next指向null，此时之前b.next指向的null也变成了游离态
 */
public class BM1翻转链表24 {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next=null;
        return newHead;
    }
    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
    public ListNode reverseList1(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
    @Test
    public void test(){
        ListNode head = new ListNode();
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        head.next = listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        listNode5.next=null;
        ListNode result = reverseList1(head);
        while (result!=null){
            System.out.println(result.val);
            result=result.next;
        }
    }
}
